package simple;

import data.TreeNode;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/6/13 21:25
 */
public class No112_路径总和 {
    public static void main(String[] args) {
        Solution112 solution112 = new Solution112();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);

        boolean res = solution112.hasPathSum(root, 22);
        System.out.println(res);
    }
}

class Solution112 {
    public boolean hasPathSum(TreeNode root, int sum) {
        return hasPathSum(root, 0, sum);
    }

    //add:递归过程中所有节点的和
    public boolean hasPathSum(TreeNode root, int add, int sum) {
        if (root == null) {
            return false;
        }
        //add:上一些节点的和 + 当前节点的和
        add += root.val;
        if (root.left == null && root.right == null) {
            return add == sum;
        } else {
            //下一次递归开始
            return hasPathSum(root.left, add, sum) || hasPathSum(root.right, add, sum);
        }

    }
}

